package langsi.ssm.controller;

import java.util.ArrayList;
import java.util.List;

import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.servlet.ModelAndView;

/**
 * 二分查找
 * 
 * @author SevenKey
 *
 */
@Controller()
@RequestMapping("/query")
public class BinaryController {

	@RequestMapping(value = "/binarySearchByKey", method = { RequestMethod.POST, RequestMethod.GET })
	public ModelAndView binarySearchByKey(Integer key) {
		int[] array = new int[101];
		for (int i = 1; i <= 100; i++) {
			array[i] = i;
		}
		int result = -1;
		if (key != null) {
			result = BinSearch(array, 100, key);// 非递归查找
			// result = BinSearch(array, 0, 99, key);// 递归查找
		}
		String message = "";
		if (result == -1) {
			message = "数组中不存在key";
		} else {
			message = "key存放在数组的" + result + "下标出";
		}
		ModelAndView modelAndView = new ModelAndView();
		modelAndView.addObject("message",message);
		modelAndView.setViewName("binaryresult");
		return modelAndView;
	}

	/**
	 * 非递归查找
	 * 
	 * @param Array
	 *            查找的数组
	 * @param SizeOfArray
	 *            数组长度
	 * @param key
	 *            查找的值
	 * @return 下标 返回-1没找到
	 */
	public int BinSearch(int Array[], int SizeOfArray, int key) {
		int low = 0, high = SizeOfArray - 1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (key == Array[mid])
				return mid;
			if (key < Array[mid])
				high = mid - 1;
			if (key > Array[mid])
				low = mid + 1;
		}
		return -1;
	}

	/**
	 * 递归查找
	 * 
	 * @param Array
	 *            查找的数组
	 * @param low
	 *            头
	 * @param high
	 *            尾
	 * @param key
	 *            查找的值
	 * @return 下标 返回-1没找到
	 */
	public int BinSearch(int Array[], int low, int high, int key) {
		if (low <= high) {
			int mid = (low + high) / 2;
			if (key == Array[mid])
				return mid;
			else if (key < Array[mid])
				return BinSearch(Array, low, mid - 1, key);
			else if (key > Array[mid])
				return BinSearch(Array, mid + 1, high, key);
		}
		return -1;
	}
}
